//
// Created by zhou on 2021/10/21.
//

#include <iostream>
using namespace std;
struct ListNode{
    int val;
    ListNode *next;
    ListNode():val(0),next(nullptr){}
    ListNode(int x):val(x),next(nullptr){}
    ListNode(int x,ListNode *next):val(x),next(next){}
};
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        int len=0;
        ListNode *p1=head;
        while(p1!= nullptr){
            p1=p1->next;
            len++;
        }
        int node;
        p1=head;
        if(len%2==0)node=len/2;
        else node=len/2;
        while(node>0){
            p1=p1->next;
            node--;
        }
        return p1;
    }
    ListNode* middleNode1(ListNode* head) {
        ListNode *slow=head;
        ListNode *fast=head;
        while(fast->next!= nullptr){
            slow=slow->next;
            fast=fast->next;
            if(fast->next!= nullptr)
                fast=fast->next;
        }
        return slow;


    }
};
int main(){
    ListNode *p=new ListNode(1);
    ListNode*p1=new ListNode(2);
    ListNode *p2=new ListNode(7);
    ListNode *p3=new ListNode(3);

    ListNode *p4=new ListNode(4);
    ListNode *p5=new ListNode(5);
    p->next=p1;
    p1->next=p2;
    p2->next=p3;
    p3->next=p4;
    p4->next=p5;
    Solution solution;
    cout<<solution.middleNode1(p)->val;
}